package previous.Test_0213;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //N皇后
    List<List<String>> ret;
    List<String> path;
    char[][] a;
    boolean[] col1;
    boolean[] dig1;
    boolean[] dig2;
    public List<List<String>> solveNQueens(int n) {
        ret=new ArrayList<>();
        path=new ArrayList<>();
        a=new char[n][n];
        //列
        col1=new boolean[n];
        //主对角线
        dig1=new boolean[2*n];
        //副对角线
        dig2=new boolean[2*n];
        //初始化
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i],'.');
        }
        dfs(0,n);
        return ret;
    }
    public void dfs(int row,int n){
        //递归出口
        if(row==n){
            path=new ArrayList<>();
            for (int i = 0; i < n; i++) {
                path.add(new String(a[i]));
            }
            ret.add(new ArrayList<>(path));
        }
        for (int col = 0; col < n; col++) {
            //合法
            if(col1[col]==false && dig1[row-col+n]==false && dig2[col+row]==false){
                a[row][col]='Q';
                col1[col]=dig1[row-col+n]=dig2[col+row]=true;
                dfs(row+1,n);

                //恢复
                a[row][col]='.';
                col1[col]=dig1[row-col+n]=dig2[col+row]=false;
            }
        }
    }
    //有效的数独
    boolean[][] checkrow;
    boolean[][] checkcol;
    boolean[][][] grid;
    public boolean isValidSudoku(char[][] board) {
           //行
           checkrow=new boolean[9][10];
           //列
           checkcol=new boolean[9][10];
           //方块
           grid=new boolean[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int num=board[i][j]-'0';
                //判断是否合法有效
                if(board[i][j]!='.'){
                if(checkrow[i][num] || checkcol[j][num] || grid[i/3][j/3][num]){
                    return false;
                }
                    checkrow[i][num] = checkcol[j][num] = grid[i/3][j/3][num]=true;
                }
            }
        }
        return true;
    }
    //解数独
    boolean[][] checkrow1;
    boolean[][] checkcol1;
    boolean[][][] grid1;
    public void solveSudoku(char[][] board) {
          checkrow1=new boolean[9][10];
          checkcol1=new boolean[9][10];
          grid1=new boolean[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int num=board[i][j]-'0';
                if(board[i][j]!='.'){
                    checkrow1[i][num] = checkcol1[j][num] = grid1[i/3][j/3][num]=true;
                }
            }
        }
          dfs(board);
    }
    public boolean dfs(char[][] board){
        //递归出口
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                //当符号位‘.'，放入可能得元素
                if(board[i][j]=='.'){
                    //如果没有重复元素，放入
                    for (int k = 1; k <=9 ; k++) {
                        //剪枝
                        if(!checkrow1[i][k] && !checkcol1[j][k] && !grid1[i/3][j/3][k] ){
                            board[i][j]=(char)(k+'0');
                            checkrow1[i][k] = checkcol1[j][k] = grid1[i/3][j/3][k]=true;
                            if(dfs(board)==true) return true;
                            //恢复
                            board[i][j]='.';
                            checkrow1[i][k] = checkcol1[j][k] = grid1[i/3][j/3][k]=false;
                        }
                    }
                    //试了之后，依旧没有返回，说明9个数不行
                    return false;
                }
            }
            }
        //已经填满
        return true;
        }

}
